package org.getOffer.offer10_2;

/**
 * @Author yu
 * @Date 2021/10/10
 */
public class Solution {

    public static void main(String[] args) {

        Solution solution = new Solution();
        System.out.println(solution.numWays(45));

    }

    public int numWays(int n) {

        if (n == 1 || n == 0) {
            return 1;
        }
        if (n == 2) {
            return 2;
        }
        //return (numWays(n-1) + numWays(n-2)) % 1000000007;

        return numWays(n-1) + numWays(n-2);

    }

//    public int numWays(int n) {
//        int i=1,j=1,sum=0;
//
//        for (int m=0;m<n;m++){
//            sum=(i+j)%1000000007;
//            i=j;
//            j=sum;
//        }
//        return i;
//
//    }

}
